package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

import java.util.Stack;

class RemoveKDigits {
    // 2022-08-27 15:12:11
    public static void main(String[] args) {
        Solution solution = new RemoveKDigits().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeKdigits(String num, int k) {
            // 不能简单的移除 0 或者 最高位
            // 如果每次都按最优的决策？即 k=1时怎么做最优？
//        如果当前遍历的数比栈顶大，符合递增，是满意的，让它入栈。
//        如果当前遍历的数比栈顶小，栈顶立刻出栈
            int remain = num.length() - k;
            Stack<Character> stack = new Stack<>();
            stack.push(num.charAt(0));
            for (int i = 1; i < num.length(); i++) {
                while (k > 0 && !stack.isEmpty() && num.charAt(i) < stack.peek()) {
                    stack.pop();
                    k--;
                }
                stack.push(num.charAt(i));
            }
            StringBuilder ans = new StringBuilder();
            while (!stack.isEmpty()) {
                ans.append(stack.pop());
            }
            String s = ans.reverse().substring(0, remain);
            while (s.startsWith("0")) {
                s = s.substring(1);
            }
            if (s.equals("")) {
                s = "0";
            }
            return s;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}